<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 最大子序和
           输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
           输出：6
           解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
        */
        /* 
            时间：O(n)
            空间：O(n)
        */
        // 贪心算法
        var maxSubArray = function(nums) {
            let len = nums.length;
            let dp = new Array(len).fill(0)
            // 初始化，dp[0]必须是nums[0]的值
            dp[0] = nums[0]
            let result = 0
            for (let i = 1; i < len; i++) {
                // 要么从头开始计算子数组，要么当前的值加入之前的子数组
                dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
                if (dp[i] > result) result = dp[i]
            }
            return result
        };
        console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]));
        console.log(maxSubArray([5,4,-1,7,8]));
    </script>
</body>

</html>